package com.honeywen.mymvc.leetcode;

/**
 * 155. 最小栈
 * https://leetcode-cn.com/problems/min-stack/submissions/
 * @author wangwei
 * @date 2019/4/2
 */
public class MinStack {

    private int[] stack;
    private int[] mins;
    private int index;
    private int minIndex;
    private int capacity;


    /**
     * ["MinStack","push","push","push","top","pop","getMin","pop","getMin","pop","push","top","getMin","push","top","getMin","pop","getMin"]
     * [[],[2147483646],[2147483646],[2147483647],[],[],[],[],[],[],[2147483647],[],[],[-2147483648],[],[],[],[]]
     *
     * ["MinStack","push","push","push","getMin","pop","top","getMin"]
     * [[],[-2],[0],[-3],[],[],[],[]]
     *
     * @param args
     */

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int min1 = minStack.getMin();
        minStack.pop();
        int top2 = minStack.top();
        int min3 = minStack.getMin();

    }

    /**
     * initialize your data structure here.
     */
    public MinStack() {

        index = -1;
        minIndex = 0;
        capacity = 10;
        stack = new int[capacity];
        mins = new int[capacity];


    }

    public void push(int x) {

        index++;

        if (index > capacity - 1) {
            // 扩容
            expand();

        }
        stack[index] = x;

        if (x < getMin()) {
            minIndex++;

            mins[minIndex] = index;
        }



    }


    private void expand() {

        int[] tmp = new int[2 * capacity];
        System.arraycopy(stack, 0, tmp, 0, capacity);
        stack = tmp;

        tmp = new int[2 * capacity];
        System.arraycopy(mins, 0, tmp, 0, capacity);
        mins = tmp;

        capacity = capacity * 2;


    }

    public void pop() {

        if (index == mins[minIndex]) {
            mins[minIndex] = 0;
            minIndex--;
        }

        stack[index] = 0;
        index--;

    }

    public int top() {

        if (index < 0) {
            return 0;
        }

        return stack[index];
    }

    public int getMin() {

        if (minIndex < 0) {
            return stack[0];
        }

        return stack[mins[minIndex]];

    }

}
